import random


def adjust_heap(l, i, size):
    """
    调整堆
    :param l:
    :param i:
    :param size:
    :return:
    """
    lc = 2*i + 1
    rc = lc + 1
    max = i
    if i < size//2:
        if lc < size and l[lc] > l[max]:
            max = lc
        if rc < size and l[rc] > l[max]:
            max = rc
        if max != i:
            l[max], l[i] = l[i], l[max]
            adjust_heap(l, max, size)


def heap_sort(arr):
    """
    堆排
    :param arr:
    :return:
    """
    # 建堆
    for i in range(len(arr)//2)[::-1]:
        adjust_heap(arr, i, len(arr))
    # 排序 大顶堆 每次最上面的最大值与最后的值交换 然后不断缩减排序范围
    for i in range(len(arr))[::-1]:
        arr[0], arr[i] = arr[i], arr[0]
        adjust_heap(arr, 0, i)
    return arr


def get_random_number(num):
    lists = []
    while len(lists) < num:
        lists.append(random.randint(0, 100))
    return lists


lists = get_random_number(10)
print(lists)
print(heap_sort(lists))